package sun;


import java.util.Arrays;

public class Cruise {
    public static void main(String[] args) {
        int INF = Integer.MAX_VALUE;
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verNumber=0;
        int matrix[][] = {
                {0  , 12 , INF, INF, INF, 16 , 14},
                {12 , 0  , 10 , INF, INF, 7  , INF},
                {INF, 10 , 0  , 3  , 5  , 6  , INF},
                {INF, INF, 3  , 0  , 4  , INF, INF},
                {INF, INF, 5  , 4  , 0  , 2  , 8},
                {16 , 7  , 6  , INF, 2  , 0  , 9},
                {14 , INF, INF, INF, 8  , 9  , 0},
        };
        for (int i = 0; i <vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if (matrix[i][j]!=INF){
                    verNumber++;
                }
            }
        }
        Min min = new Min(vertexs,matrix,verNumber);
        min.Cruise();
    }
}

/**
 * @vertexs 存储顶点
 * @matrixs 存储边
 * @INF 表示这条边不通
 */
class Min{
    char[] vertex;
    int matrix[][];
    int INF=Integer.MAX_VALUE;
    int verNumber=0;
    public Min(char[] vertexs, int[][] matrix,int verNumber) {
        this.vertex = vertexs;
        this.matrix = matrix;
        this.verNumber=verNumber;
    }


    public int getEdg(char ch){//返回要查找的顶点的下标
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i]==ch){
                return i;
            }
        }
        return -1;
    }

    public void sort(EdgeData[] edgeData){//将边以权值从小到大排序（冒泡）
        for (int i = 0; i < edgeData.length-1; i++) {
            for (int j = 0; j < edgeData.length-1-i; j++) {
                if (edgeData[j+1].wight<edgeData[j].wight){
                EdgeData temEdg=edgeData[j];
                edgeData[j]=edgeData[j+1];
                edgeData[j+1]=temEdg;
                }
            }
        }

    }

    public int getEnd(int[] end,int i){//返回当前顶点的终点的下标
        while (end[i]!=0){
            i=end[i];
        }
        return i;
    }

    public EdgeData[] getmatrix(){//将可以通行的边装入数组中
        int index=0;
        EdgeData[] edgeData=new EdgeData[verNumber];
        for (int i = 0; i < vertex.length; i++) {
            for (int j = i+1; j < vertex.length; j++) {
                if (matrix[i][j]!=INF) {
                    edgeData[index++]=new EdgeData(vertex[i],vertex[j],matrix[i][j]);
                }
            }
        }
        return edgeData;
    }



    public void Cruise(){//克鲁斯
        EdgeData[] res=new EdgeData[vertex.length-1];//用于存放最小生成树
        int index=0;
        EdgeData[] edg=getmatrix();
        sort(edg);
        int[] ends=new int[verNumber];//用于保存已有最小生成树中的顶点在最小生成树的终点

        for (int i = 0; i < verNumber; i++) {
            int m1=getEdg(edg[i].start);//获取边头顶点下标
            int m2=getEdg(edg[i].end);//获取边尾顶点下标

            int m=getEnd(ends,m1);//获取边头顶点d终点下标
            int n=getEnd(ends,m2);//获取边尾顶点的终点下标
            if (m!=n){//如果相同就放弃这条边
                ends[m]=n;
                res[index++]=edg[i];
            }

        }

        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
        System.out.println(Arrays.toString(res));






    }


}






/**
 * @start 边的上一个顶点
 * @end 边的下一个顶点
 * @wight 顶点的权值
 */
class EdgeData{
    char start;
    char end;
    int wight;

    public EdgeData(char start, char end, int wight) {
        this.start = start;
        this.end = end;
        this.wight = wight;
    }

    @Override
    public String toString() {
        return "EdgeData{" +
                "start=" + start +
                ", end=" + end +
                ", wight=" + wight +
                '}';
    }
}